package _2022.hot100._160_相交链表;

import java.util.HashSet;

/**
 * @author： YHSimon
 * @date： 2022-05-06 15:08
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {

    //5 ms
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        HashSet<ListNode> visited = new HashSet<>();
        ListNode tmp = headA;
        while (tmp != null) {
            visited.add(tmp);
            tmp = tmp.next;
        }
        tmp = headB;
        while (tmp != null) {
            if (visited.contains(tmp)) {
                return tmp;
            }
            tmp = tmp.next;
        }
        return null;
    }


    // 1ms
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1 = 0;
        int len2 = 0;
        ListNode tmpA = headA;
        ListNode tmpB = headB;
        while (tmpA != null) {
            len1++;
            tmpA = tmpA.next;
        }
        while (tmpB != null) {
            len2++;
            tmpB = tmpB.next;
        }
        tmpA = headA;
        tmpB = headB;

        if (len1 <= len2) {
            for (int i = 0; i < len2 - len1; i++) {
                tmpB = tmpB.next;
            }
        } else {
            for (int i = 0; i < len1 - len2; i++) {
                tmpA = tmpA.next;
            }
        }
        while (tmpA != null && tmpB != null) {
            if (tmpA == tmpB) {
                return tmpA;
            }
            tmpA = tmpA.next;
            tmpB = tmpB.next;
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode listA = new ListNode(4);
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(8);
        ListNode l3 = new ListNode(4);
        ListNode l4 = new ListNode(5);
        listA.next = l1;
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;

        ListNode listB = new ListNode(5);
        ListNode l5 = new ListNode(6);
        ListNode l6 = new ListNode(1);
        ListNode l7 = new ListNode(8);
        ListNode l8 = new ListNode(4);
        ListNode l9 = new ListNode(5);
        listB.next = l5;
        l5.next = l6;
        l6.next = l7;
        l7.next = l8;
        l8.next = l9;

        Solution solution = new Solution();
        System.out.println(solution.getIntersectionNode2(listA, listB));
    }
}
